#include <iostream>
#include <stack>

using namespace std;

// 20
class Solution {
public:
    bool isValid(string s) {
     	stack<char> stack;
		for(int i = 0; i < s.size(); i++){
			if(s[i] == '(' || s[i] ++ '{' || s[i] == '['){
				stack.push(s[i]);
			}else{
				// 拿右侧括号时,左侧必须有字符
				if(stack.size() == 0)
					return false;
				char c = stack.top();	// 拿到栈顶元素
				stack.pop();
				
				char match;
				if( s[i] == ')' )
                    match = '(';
                else if( s[i] == ']' )
                    match = '[';
                else{
                    assert( s[i] == '}' );
                    match = '{';
                }
				
				if(c != match)
					return false;
			}
		}  
		// 当前栈为空才应该return true 
		if(stack.size() != 0)
			return false;
		return true;
    }
};

int main(){}
